import java.util.List;
// 力扣120. 三角形最小路径和
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // 初始化 dp 数组为三角形的最后一行
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }

        // 从倒数第二行开始向上遍历
        for (int i = n - 2; i >= 0; i--) {
            // 遍历当前行的每一列
            for (int j = 0; j <= i; j++) { // 第 i 行有 i+1 个元素，所以 j 从 0 到 i
                // 更新 dp[j]：当前行的值 + 下一行两个相邻结果中较小的一个
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }
        return dp[0];
    }
}



// 力扣63. 不同路径 II
class Solution1 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        // 如果起点或终点有障碍物，直接返回0
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }

        // 创建dp数组，存储到达每个位置的路径数
        int[][] dp = new int[m][n];

        // 初始化第一行
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

        // 初始化第一列
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }

        // 填充dp数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 如果当前位置没有障碍物，则路径数等于上方和左方的路径数之和
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
                // 如果有障碍物，路径数保持为0（数组默认值）
            }
        }

        return dp[m-1][n-1];
    }
}
